package 剑指offer;

public class p22链表中倒数第k个节点 {
    public ListNode getKthFromEnd1(ListNode head, int k) {
        int count=0;
        ListNode cur=head;
        while (cur!=null) {
            count++;
            cur=cur.next;
        }

        cur=head;
        for (int i = 0; i <count-k; i++) {
            cur=cur.next;
        }
        return cur;
    }

    public ListNode getKthFromEnd(ListNode head, int k) {
        //双指针
        ListNode former=head;
        ListNode latter=head;

        //让 former指针先向前走k步
        for (int i = 0; i <k; i++) {
            former=former.next;
        }

        //两个指针每轮同时向前走一个，直到former指针出局
        while (former!=null) {
            former=former.next;
            latter=latter.next;
        }
        return latter;
    }
}
